package com.zdp.util;

import java.util.ArrayList;
import java.util.List;

public class Heap {

    /*
    * 创建堆
    * */
    public void createHeap(int[] nums){
        // 传入一个数组
        for(int i=(nums.length-2)/2;i>=0;i--){
            // 调整堆，从下到上，从左到右
            adjustHeap(nums,i,nums.length-1);
        }
    }
    /*
    * 调整堆
    * */
    public void adjustHeap(int[] nums,int s,int length){
        int temp = nums[s]; // 要调整的树的根结点
        for(int i=2*s+1;i<=length;i=(i*2)+1){
            // 找到孩子结点中较大的那一个
            // 因为我们的调整是从下到上的
            // 所以可以看成 以孩子结点为根的树 都是调整完毕的堆
            if(i<length&&nums[i]<nums[i+1]){
                i++;
            }
            // 判断根结点是否大于孩子结点
            if(temp>=nums[i]){
                // 大于就不需要再进行调整了
                break;
            }
            // 若根节点小于孩子结点，则将孩子结点与根节点
            // 孩子结点与根节点交换后，这时候，以孩子结点作为根的树 也要进行调整了
            nums[s] = nums[i];
            s = i; // 切换根 ---> 相当于切换要调整的堆
            // 现在要调整的堆就是 以刚才与根节点交换的那个孩子结点为根的堆
        }
        // 调整完毕，将原本的根节点的值插入到相应的位置
        nums[s] = temp;
    }
    /*
    * 堆排序
    * */
    public List<Integer> HeapSort(int[] nums){
        createHeap(nums);
        List<Integer> result = new ArrayList<>();
        // 将堆的头元素放到末尾，然后进行调整
        for(int i =nums.length-1;i>=0;i--){
            swap(nums,0,i);
            result.add(nums[i]);
            // 调整
            adjustHeap(nums,0,i-1);
        }
        return result;
    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
